#include <iostream>
#include <memory>
#include <stdexcept>
#include <iterator>
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

template<typename Iterator>
struct iterator_traits 
{
    using difference_type = typename Iterator::difference_type;
    using value_type = typename Iterator::value_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
    using iterator_category = typename Iterator::iterator_category;
};

template<typename T>
struct iterator_traits<T*> 
{
    using difference_type = ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using iterator_category = random_access_iterator_tag;
};

template<typename T>
struct iterator_traits<const T*> 
{
    using difference_type = ptrdiff_t;
    using value_type = T;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = random_access_iterator_tag;
};

// Vector迭代器实现
template<typename T>
class VectorIterator 
{
public:
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T*;
    using reference = T&;

private:
    pointer current;

public:
    // 构造函数
    VectorIterator() : current(nullptr) {}
    explicit VectorIterator(pointer ptr) : current(ptr) {}

    // 解引用操作
    reference operator*() const { return *current; }
    pointer operator->() const { return current; }

    // 自增自减操作
    VectorIterator& operator++() 
    {
        ++current;
        return *this;
    }

    VectorIterator operator++(int) 
    {
        VectorIterator tmp = *this;
        ++current;
        return tmp;
    }

    VectorIterator& operator--() 
    {
        --current;
        return *this;
    }

    VectorIterator operator--(int) 
    {
        VectorIterator tmp = *this;
        --current;
        return tmp;
    }

    // 算术运算
    VectorIterator& operator+=(difference_type n) 
    {
        current += n;
        return *this;
    }

    VectorIterator operator+(difference_type n) const 
    {
        return VectorIterator(current + n);
    }

    VectorIterator& operator-=(difference_type n) 
    {
        current -= n;
        return *this;
    }

    VectorIterator operator-(difference_type n) const 
    {
        return VectorIterator(current - n);
    }

    difference_type operator-(const VectorIterator& other) const 
    {
        return current - other.current;
    }

    // 下标操作
    reference operator[](difference_type n) const 
    {
        return current[n];
    }

    // 比较操作
    bool operator==(const VectorIterator& other) const 
    {
        return current == other.current;
    }

    bool operator!=(const VectorIterator& other) const 
    {
        return !(*this == other);
    }

    bool operator<(const VectorIterator& other) const 
    {
        return current < other.current;
    }

    bool operator>(const VectorIterator& other) const 
    {
        return other < *this;
    }

    bool operator<=(const VectorIterator& other) const 
    {
        return !(other < *this);
    }

    bool operator>=(const VectorIterator& other) const 
    {
        return !(*this < other);
    }
};

// Const迭代器实现
template<typename T>
class VectorConstIterator 
{
public:
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;

private:
    pointer current;

public:
    // 构造函数
    VectorConstIterator() : current(nullptr) {}
    explicit VectorConstIterator(pointer ptr) : current(ptr) {}
    VectorConstIterator(const VectorIterator<T>& other) : current(other.operator->()) {}

    // 解引用操作
    reference operator*() const { return *current; }
    pointer operator->() const { return current; }

    // 自增自减操作
    VectorConstIterator& operator++() 
    {
        ++current;
        return *this;
    }

    VectorConstIterator operator++(int) 
    {
        VectorConstIterator tmp = *this;
        ++current;
        return tmp;
    }

    VectorConstIterator& operator--() 
    {
        --current;
        return *this;
    }

    VectorConstIterator operator--(int) 
    {
        VectorConstIterator tmp = *this;
        --current;
        return tmp;
    }

    // 算术运算
    VectorConstIterator& operator+=(difference_type n) 
    {
        current += n;
        return *this;
    }

    VectorConstIterator operator+(difference_type n) const 
    {
        return VectorConstIterator(current + n);
    }

    VectorConstIterator& operator-=(difference_type n) 
    {
        current -= n;
        return *this;
    }

    VectorConstIterator operator-(difference_type n) const 
    {
        return VectorConstIterator(current - n);
    }

    difference_type operator-(const VectorConstIterator& other) const 
    {
        return current - other.current;
    }

    // 下标操作
    reference operator[](difference_type n) const 
    {
        return current[n];
    }

    // 比较操作
    bool operator==(const VectorConstIterator& other) const 
    {
        return current == other.current;
    }

    bool operator!=(const VectorConstIterator& other) const 
    {
        return !(*this == other);
    }

    bool operator<(const VectorConstIterator& other) const 
    {
        return current < other.current;
    }

    bool operator>(const VectorConstIterator& other) const 
    {
        return other < *this;
    }

    bool operator<=(const VectorConstIterator& other) const 
    {
        return !(other < *this);
    }

    bool operator>=(const VectorConstIterator& other) const 
    {
        return !(*this < other);
    }
};

// Vector实现
template<typename T>
class Vector {
public:
    using value_type = T;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using iterator = VectorIterator<T>;
    using const_iterator = VectorConstIterator<T>;

private:
    pointer data_;
    size_type size_;
    size_type capacity_;

    // 重新分配内存
    void reallocate(size_type new_capacity) {
        pointer new_data = new value_type[new_capacity];
        for (size_type i = 0; i < size_; ++i) {
            new_data[i] = std::move(data_[i]);
        }
        delete[] data_;
        data_ = new_data;
        capacity_ = new_capacity;
    }

public:
    // 构造函数
    Vector() : data_(nullptr), size_(0), capacity_(0) {}

    explicit Vector(size_type count)
        : data_(new value_type[count]), size_(count), capacity_(count) {
        for (size_type i = 0; i < count; ++i) {
            data_[i] = value_type();
        }
    }

    // 析构函数
    ~Vector() {
        delete[] data_;
    }

    // 容量相关
    size_type size() const { return size_; }
    size_type capacity() const { return capacity_; }
    bool empty() const { return size_ == 0; }

    void reserve(size_type new_capacity) {
        if (new_capacity > capacity_) {
            reallocate(new_capacity);
        }
    }

    // 元素访问
    reference operator[](size_type pos) { return data_[pos]; }
    const_reference operator[](size_type pos) const { return data_[pos]; }

    reference at(size_type pos) {
        if (pos >= size_) {
            throw std::out_of_range("Vector index out of range");
        }
        return data_[pos];
    }

    const_reference at(size_type pos) const {
        if (pos >= size_) {
            throw std::out_of_range("Vector index out of range");
        }
        return data_[pos];
    }

    // 修改器
    void push_back(const T& value) {
        if (size_ == capacity_) {
            size_type new_capacity = (capacity_ == 0) ? 1 : capacity_ * 2;
            reallocate(new_capacity);
        }
        data_[size_++] = value;
    }

    void pop_back() {
        if (!empty()) {
            --size_;
        }
    }

    void clear() {
        size_ = 0;
    }

    // 迭代器
    iterator begin() { return iterator(data_); }
    iterator end() { return iterator(data_ + size_); }
    const_iterator begin() const { return const_iterator(data_); }
    const_iterator end() const { return const_iterator(data_ + size_); }
    const_iterator cbegin() const { return const_iterator(data_); }
    const_iterator cend() const { return const_iterator(data_ + size_); }
};

// 测试代码
int main() {
    try {
        Vector<int> vec;

        // 测试push_back
        std::cout << "Testing push_back:\n";
        for (int i = 0; i < 5; ++i) {
            vec.push_back(i);
            std::cout << "Added " << i << ", size: " << vec.size()
                << ", capacity: " << vec.capacity() << "\n";
        }

        // 测试迭代器遍历
        std::cout << "\nIterator traversal: ";
        for (const auto& value : vec) {
            std::cout << value << " ";
        }
        std::cout << "\n";

        // 测试随机访问
        std::cout << "\nRandom access:\n";
        auto it = vec.begin();
        it += 2;
        std::cout << "Iterator + 2: " << *it << "\n";
        std::cout << "Using []: " << vec[2] << "\n";

        // 测试const迭代器
        const Vector<int>& const_vec = vec;
        std::cout << "\nConst iterator traversal: ";
        for (auto it = const_vec.begin(); it != const_vec.end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << "\n";

    }
    catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
        return 1;
    }

    return 0;
}
